#pragma once
#include <iostream>
#include <utility>
#include <vector>

namespace lw
{
	template<class K>
	struct Equal
	{
		bool operator()(const K& k1, const K& k2)
		{
			return k1 == k2;
		}
	};

	template<class T>
	struct Hash
	{
		size_t operator()(const T& val)
		{
			return val;
		}
	};
	template<>
	struct Hash<std::string>
	{
		size_t operator()(const std::string& s)
		{
			size_t hash = 0;
			for (auto ch : s)
			{
				hash += ch;
				hash *= 31;
			}
			return hash;
		}
	};
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};
	template<class K, class T, class KeyOfT, class Hash, class Equal>
	class HashBucket;

	template<class K, class T, class KeyOfT, class Hash, class Equal>
	struct __HashBucket__Iterator
	{
		typedef HashNode<T> Node;
		typedef HashBucket<K, T, KeyOfT, Hash, Equal> HT;
		typedef __HashBucket__Iterator<K, T, KeyOfT, Hash, Equal> Self;
		Node* _node;
		HT* _ht;
		__HashBucket__Iterator(Node* node, HT* ht)
			:_node(node)
			,_ht(ht)
		{}

		T& operator*()
		{
			return _node->_data;
		}
		T* operator->()
		{
			return &(operator*());
		}

		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				size_t pos = Hash()(KeyOfT()(_node->_data)) % _ht->BucketSize();
				pos++;
				while (pos < _ht->BucketSize())
				{
					Node* curr = _ht->Bucket(pos);
					if (curr)
					{
						_node = curr;
						break;
					}
					pos++;
				}
				if(pos == _ht->BucketSize())
					_node = nullptr;
			}
			return *this;
		}
		Self operator++(int)
		{
			Self tmp(*this);
			++(*this);
			return tmp;
		}

		operator bool()
		{
			return _node;
		}

	};

	template<class K, class T, class KeyOfT, class Hash, class Equal>
	class HashBucket
	{
		typedef HashNode<T> Node;
	public:
		typedef __HashBucket__Iterator<K, T, KeyOfT, Hash, Equal> iterator;
		iterator begin()
		{
			size_t i = 0;
			while (i < _tables.size())
			{
				if (_tables[i])
				{
					return iterator(_tables[i], this);
				}
				i++;
			}
			return end();
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}
		HashBucket()
			:_tables(10, nullptr)
		{}
		~HashBucket()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				Node* curr = _tables[i];
				while (curr)
				{
					Node* next = curr->_next;
					delete curr;
					curr = next;
				}
				_tables[i] = nullptr;
			}
		}
		std::pair<iterator, bool> Insert(const T& data)
		{
			iterator ret = Find(KeyOfT()(data));
			if (ret)
				return std::make_pair(ret, this);
			if (_n == _tables.size())
			{
				std::vector<Node*> hs(_tables.size() * 2, nullptr);
				for (int i = 0; i < _tables.size(); i++)
				{
					Node* curr = _tables[i];
					while (curr)
					{
						Node* next = curr->_next;

						size_t pos = Hash()(KeyOfT()(curr->_data)) % hs.size();
						curr->_next = hs[pos];
						hs[pos] = curr;

						curr = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(hs);
			}

			size_t pos = Hash()(KeyOfT()(data)) % _tables.size();

			Node* node = _tables[pos];
			Node* newnode = new Node(data);

			newnode->_next = node;
			_tables[pos] = newnode;
			_n++;
			return std::make_pair(iterator(newnode, this), true);
		}
		bool Erase(const K& key)
		{
			auto erasepos = Find(key);
			if (erasepos == nullptr)
				return false;
			size_t pos = Hash()(key) % _tables.size();
			Node* curr = _tables[pos];
			if (curr == erasepos)
			{
				_tables[pos] = curr->_next;
				delete curr;
			}
			else
			{
				while (curr->_next != erasepos)
					curr = curr->_next;
				Node* del = curr->_next;
				curr->_next = del->_next;
				delete del;
			}
			_n--;
			return true;
		}
		iterator Find(const K& key)
		{
			size_t pos = Hash()(key) % _tables.size();

			Node* curr = _tables[pos];
			while (curr)
			{
				if (Equal()(KeyOfT()(curr->_data), key))
					return iterator(curr, this);
				curr = curr->_next;
			}
			return iterator(nullptr, this);
		}
		size_t BucketSize() const
		{
			return _tables.size();
		}
		Node* Bucket(size_t i)
		{
			return _tables[i];
		}
	private:
		std::vector<Node*> _tables;
		size_t _n = 0;
	};

}